package Graph;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;


public class Graph {
	
	private HashMap<String,Noeud> map;
	
	public Graph()
	{
		map = new HashMap<String, Noeud>();
	}
	
	public void addNoeud(String id)
	{
		map.put(id, new Noeud(id));
	}

	public void addNoeud(Noeud n)
	{
		map.put(n.getName(), n);
	}
	
	public boolean isPresent(String id)
	{
		return map.containsKey(id);
	}
	
	public Chemin pathTo(String from, String to)
	{
		if(from.equals(to))
			return new Chemin(from);
		if(isPresent(from) && isPresent(to))
		{
			return this.pathDij(from, to);
		}
		else
			return null;
	}
	
	private Chemin pathDij(String from, String to)
	{
		ArrayList<Chemin> list = new ArrayList<Chemin>();
		Noeud depart = map.get(from);
		Noeud arrive = map.get(to);
		HashMap<Noeud,Integer> table = new HashMap<Noeud,Integer>();
		boolean find = false;
		
		list.add(new Chemin(depart.getName()));
		
		Chemin bestChemin = list.get(0);
		Arete bestArete = depart.getAretes().get(0);
		
		
		while(!find)
		{
			int i= 1;
			ArrayList<Chemin>del = new ArrayList<Chemin>();
			
			for(Chemin c : list)
			{
				if(c.completementVisite(map.get(c.getDernierNoeud())))
					del.add(c);
				else 
					bestChemin = c; 
			}
			
			for(Chemin c : del)
				list.remove(c);
			int poids; 
			Noeud n = map.get(bestChemin.getDernierNoeud());
			if(list.size() == 0 && bestChemin.completementVisite(n))
				return null;
			if(bestChemin.getListNoeud().size() > 50)
				return null;
			boolean init = false;
			bestArete= null;
			i =0;
			while(!init)
			{
				bestArete = n.getAretes().get(i);
				if(!bestChemin.isNodeVisited(bestArete.getArrive().getName()))
				 init = true;
				else
					i++;
			}
				
			poids = bestArete.getPoids()+bestChemin.getPoids();
			
			for(Chemin c : list)
			{
				n = map.get(c.getDernierNoeud());
				for(Arete a : n.getAretes())
				{
					int p = a.getPoids()+c.getPoids(); 
					if(( p < poids) && 
													!(c.isNodeVisited(a.getArrive().getName()))
														&& (!table.containsKey(a.getArrive()) || p < table.get(a.getArrive())))
					{
						table.put(n,p);
						poids = a.getPoids()+c.getPoids();
						bestChemin = c;
						bestArete = a;
					}
					else if(table.containsKey(a.getArrive()))
						if( p > table.get(a.getArrive()))
							c.setVisited(n.getName());
				}
			}
			
			Chemin tmp = bestChemin;
			
			if(tmp.completementVisite(map.get(tmp.getDernierNoeud())))
				list.remove(tmp);
			
			bestChemin = bestChemin.newFrom(bestArete.getArrive().getName());
			bestChemin.addNoeud(bestArete.getArrive().getName(), bestArete.getPoids());
			bestChemin.setVisited(bestChemin.getDernierNoeud());
			list.add(bestChemin);
			find = (bestArete.getArrive() == arrive);
			
		}
	return bestChemin;
		
	}
	
	public Noeud getNoeud(String id)
	{
		if(map.containsKey(id))
			return map.get(id);
			else 
				return null;
	}
	
	public Map<String, Noeud> getMap()
	{
		return map;
	}

	public Chemin findNoeud(String start)
	{
		int size = 30;
		 
		Chemin ch = new Chemin(start);
		HashSet<String> noeuds = new HashSet<String>();
		HashSet<Chemin>chemins = new HashSet<Chemin>();
		Chemin c = search(ch,size,noeuds,chemins);
		if(c != null)
			return c;
		else if(!chemins.isEmpty())
		{
			Chemin f = null;
			Iterator<Chemin> it = chemins.iterator();
			f = it.next();
			while(it.hasNext())
			{
				c = it.next();
				if(f.getListNoeud().size() < c.getListNoeud().size())
					f = c;
			}
			return f;
		}
		return null;
	}
	
	public Chemin findNoeud(String start, int size)
	{
		if(size <= 0)
			size =1;
		
		Chemin ch = new Chemin(start);
		HashSet<String> noeuds = new HashSet<String>();
		HashSet<Chemin>chemins = new HashSet<Chemin>();
		Chemin c = search2(ch,size,noeuds,chemins);
		if(c != null)
			return c;
		else if(!chemins.isEmpty())
		{
			Chemin f = null;
			Iterator<Chemin> it = chemins.iterator();
			f = it.next();
			while(it.hasNext())
			{
				c = it.next();
				if(f.getListNoeud().size() < c.getListNoeud().size())
					f = c;
			}
			return f;
		}
		return null;
	}
	
	public Chemin search(Chemin ch, int size, HashSet<String>noeuds, HashSet<Chemin> chemins)
	{
		noeuds.add(ch.getDernierNoeud());
		for(Arete a :getNoeud(ch.getDernierNoeud()).getAretes())
		{
			if(!a.getArrive().getVisit() && !noeuds.contains(a.getArrive()))
			{
				noeuds.add(a.getArrive().getName());
				return  ch.newFrom(a.getArrive().getName());
			}
			else 
				chemins.add(ch.newFrom(a.getArrive().getName()));
			
		}
		
		if(size > 0)
		{
			for(Arete a :getNoeud(ch.getDernierNoeud()).getAretes())
			{
				if(!a.getArrive().getVisit() && !noeuds.contains(a.getArrive()))
				{
					Chemin c;
					c = search(ch.newFrom(a.getArrive().getName()), size-1,noeuds,chemins);
					if(c != null )
						return c;
				}
				
			}
		}
		return null;
	}
	
	
	public Chemin search2(Chemin ch, int size, HashSet<String>noeuds,HashSet<Chemin> chemins)
	{
		noeuds.add(ch.getDernierNoeud());
		if(size == 0)
			for(Arete a :getNoeud(ch.getDernierNoeud()).getAretes())
			{
				if(!a.getArrive().getVisit() && !noeuds.contains(a.getArrive()))
				{
					noeuds.add(a.getArrive().getName());
					return  ch.newFrom(a.getArrive().getName());
					
				}
				else
					chemins.add(ch.newFrom(a.getArrive().getName()));
				
			}
		
		if(size > 0)
		{
			for(Arete a :getNoeud(ch.getDernierNoeud()).getAretes())
			{
				if(!a.getArrive().getVisit() && !noeuds.contains(a.getArrive()))
				{
					Chemin c;
					c = search2(ch.newFrom(a.getArrive().getName()), size-1,noeuds,chemins);
					if(c != null )
						return c;
					else
						chemins.add(ch.newFrom(a.getArrive().getName()));
				}
				else
					chemins.add(ch.newFrom(a.getArrive().getName()));
				
			}
		}
		return null;
	}
	
	public void clear()
	{
		map.clear();
	}
}
